package com.example.common;

import java.util.ArrayList;
import java.util.List;

public class SolutionCount {
    private static final int n = 3, N = 9;
    private boolean[][] set1;
    private boolean[][] set2;
    private boolean[][][] set3;
    private int sum;

    /**
     *
     * @param board1 初始题目（可能无解或者有多个解）
     * @return 返回数独所有解的个数
     */
    public int solve(char[][] board1) {
        if (board1 == null || board1.length == 0) {
            return 0;
        }
        char[][] board = MyUtils.copyOf(board1);//初始题目内容不能破坏，需要复制一个新数组来执行回溯
        sum = 0;//统计数独的解的个数
        set1 = new boolean[N][N];
        set2 = new boolean[N][N];
        set3 = new boolean[n][n][N];
        List<int[]> list1 = new ArrayList<>();//保存空格的坐标信息
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == '.') {
                    list1.add(new int[]{i, j});
                } else {
                    int num = board[i][j] - '1';
                    set1[i][num] = true;
                    set2[j][num] = true;
                    set3[i/n][j/n][num] = true;
                }
            }
        }
        int count = N * N - list1.size();
        //System.out.println("初始数字有" + count + "个");
        backtrack(board, 0, list1);
        return sum;
    }

    private void backtrack(char[][] board, int pos, List<int[]> list1) {
        if (pos == list1.size()) {
            sum++;
            return;
        }
        int[] arr = list1.get(pos);
        int i = arr[0], j = arr[1];//空格的行号和列号
        for (int k = 0; k < N; k++) {
            if (!set1[i][k] && !set2[j][k] && !set3[i/3][j/3][k]) {
                set1[i][k] = set2[j][k] = set3[i/3][j/3][k] = true;
                board[i][j] = (char) ('1' + k);
                backtrack(board, pos + 1, list1);
                set1[i][k] = set2[j][k] = set3[i/3][j/3][k] = false;
            }
        }
    }
}
